460. LFU Cache.go

package leetcode

import"container/list"

typeLFUCachestruct {
nodesmap[int]*list.Element
listsmap[int]*list.List
capacityint
minint
}

typenodestruct {
keyint
valueint
frequencyint
}

funcConstructor(capacityint) LFUCache {
returnLFUCache{nodes: make(map[int]*list.Element),
lists: make(map[int]*list.List),
capacity: capacity,
min: 0,
 }
}

func (this*LFUCache) Get(keyint) int {
value, ok:=this.nodes[key]
if!ok {
return-1
 }
currentNode:=value.Value.(*node)
this.lists[currentNode.frequency].Remove(value)
currentNode.frequency++
if_, ok:=this.lists[currentNode.frequency]; !ok {
this.lists[currentNode.frequency] =list.New()
 }
newList:=this.lists[currentNode.frequency]
newNode:=newList.PushBack(currentNode)
this.nodes[key] =newNode
ifcurrentNode.frequency-1==this.min&&this.lists[currentNode.frequency-1].Len() ==0 {
this.min++
 }
returncurrentNode.value
}

func (this*LFUCache) Put(keyint, valueint) {
ifthis.capacity==0 {
return
 }
ifcurrentValue, ok:=this.nodes[key]; ok {
currentNode:=currentValue.Value.(*node)
currentNode.value=value
this.Get(key)
return
 }
ifthis.capacity==len(this.nodes) {
currentList:=this.lists[this.min]
frontNode:=currentList.Front()
delete(this.nodes, frontNode.Value.(*node).key)
currentList.Remove(frontNode)
 }
this.min=1
currentNode:=&node{
key: key,
value: value,
frequency: 1,
 }
if_, ok:=this.lists[1]; !ok {
this.lists[1] =list.New()
 }
newList:=this.lists[1]
newNode:=newList.PushBack(currentNode)
this.nodes[key] =newNode
}